package LeetCode.LinkedList;

/**
 * @author : LdLtd
 * @Date : 2023/7/30
 * @Description:142. 环形链表 II
 */
public class linked_list_cycle_ii {

      //Definition for singly-linked list.
      public class ListNode {
         int val;
         ListNode next;
         ListNode(int x) {
             val = x;
              next = null;
          }
      }

    public class Solution {
          /*双指针法
          如果fast到末尾，说明没环
          设入口前路程为a，环链表有b个
          如果fast和slow相遇，此时，fast走过2s==s+nb的路程，所以s=nb
          将fast指向头结点，fast速度变为1，
          当两者相遇时，s=a+nb,fast/slow的位置即为入口a的位置
          * */
        public ListNode detectCycle(ListNode head) {
            ListNode fast=head,slow=head;
            while (true){
                if(fast==null||fast.next==null){
                    return null;
                }
                fast=fast.next.next;
                slow=slow.next;
                if(slow==fast){
                    break;
                }
            }
            fast=head;
            while (slow!=fast){
                slow=slow.next;
                fast=fast.next;
            }
            return fast;
        }
    }
}
